"""
难度：简单
翻转一棵二叉树。
示例：
输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1
"""
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
  # 递归方法实现
    def invertTree(self, root: TreeNode) -> TreeNode:
      if root == None:
        return root
      left = self.invertTree(root.left) 
      right = self.invertTree(root.right)

      root.left = right
      root.right = left

      return root

  # 层序遍历，遍历方式进行翻转
    def invertTree(self, root: TreeNode) -> TreeNode:
      if not root:
        return None
      queue = [root]

      while queue:
        curr = queue.pop(0)
        temp = curr.left
        curr.left = curr.right
        curr.right = temp

        if (curr.left != None):
          queue.append(curr.left)
        if curr.right != None:
          queue.append(curr.right)
      return root

      # 深度优先遍历方式，翻转
    def invertTree(self, root: TreeNode) -> TreeNode:
      if not root:
        return None
      stack = []
      stack.append(root)
      while stack:
        size = len(stack)
        for _ in range(size):
          curr = stack.pop()

          temp = curr.left
          curr.left = curr.right
          curr.right = temp

          if curr.right != None:
            stack.append(curr.right)
          if curr.left != None:
            stack.append(curr.left)
      return root

